Digital images are currently used in many applications, for example in new generation acquisition devices such as digital cameras or DSC (Digital Still Cameras). Furthermore, digital images are becoming more and more widely used in portable multimedia communication terminals.
Typically, a digital image is represented by a pixel matrix. The total number of pixels present in said matrix defines the spatial resolution of the image. Each pixel is identified by a pair of spatial coordinates that correspond to the position of the pixel inside the matrix and by one or more digital values associated to it, each of which represents a parameter of the pixel.
For example, three digital values are associated with each pixel in an RGB format color digital image, representative of the following parameters respectively: intensity of the red color component, intensity of the green color component and intensity of the blue color component.
In various applications, representation of a digital image as a pixel matrix is not optimal because, for example, storage of the pixel matrix can require a large quantity of memory. Moreover, a digital image represented by a pixel matrix cannot be enlarged at will without this leading to a considerable loss in quality of the enlarged image.
For this reason, a different form of representation is sometimes used, for example a representation known in the art as vector representation (or vector format).
Essentially, in a vector format, the image is represented as a plurality of non-overlapping regions or areas, also called primitives, which altogether cover the entire image. The information necessary to define the contours of said regions are stored, while the information regarding the pixel parameters comprised in each region are summarized in a few parameters generically associated with the entire region or only associated with a limited number of pixels in the region. It can be seen from the above that transformation of a digital image originally represented by a pixel matrix to a corresponding image represented by a vector format leads to a reduction in the information contained in the initial image and, therefore, to its approximation. The quantity of memory required for storage of the image is therefore reduced compared to the memory required for an image represented as a pixel matrix.
It has been observed, furthermore, that in particular applications, such as enlarging techniques and processing techniques in general that require an increase/decrease (i.e. resizing) in the spatial resolution of the image, vector representation is more convenient and efficient than pixel matrix representation.
A class of methods belonging to the state of the art to obtain a vector representation (or raster to vector conversion) starting from a digital image formed by a pixel matrix, provides for the use of triangulation, i.e. dividing into triangular areas of the initial image.
For example, triangulation techniques are known that operate by exploiting the information contained in the image (represented by the digital values associated to the parameters of the image pixels) and techniques where said type of information is not taken into consideration. These techniques are commonly indicated as “data dependent triangulation techniques” and “data independent triangulation techniques”.
For example, a data dependent triangulation technique is described in the publication “Data dependent triangulations for piecewise linear interpolation” by N. Dyn, D. Levin and S. Rippa, IMA Journal of Numerical Analysis, vol. 10, pp. 137-154, January 1990.
A data independent triangulation technique has been known since 1934 named “Delaunay triangulation”.
It has been observed how numerous raster to vector conversion methods belonging to the state of the art, even if widely used, do not guarantee satisfactory performance in terms of the dimensions occupied by the vectorized images and in terms of the measured or perceived quality of said images.